package day;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.Executors;

/**
 * 678. 有效的括号字符串
 */
public class P678 {
    /**
     * 基于栈效解：
     * 1. 如果当前符号为左括号则入栈
     * 2. 如果当前符号位右括号，
     * 2.1 栈顶元素位左括号直接消解
     * 2.2 栈顶元素为星号，尽量使用栈中的左括号消除右括号，没有左括号则使用星号进行消除
     * 3. 如果当前符号为星号, 直接入栈
     * <p>
     * 4. 最终栈为空，或栈中的星号数量>=左括号数量，则正确
     */
    public boolean checkValidString(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '*':
                case '(':
                    stack.push(c);
                    break;
                case ')':
                    if(stack.isEmpty()){
                        return false;
                    }
                    if (stack.peek() == '(') {//栈顶为左括号
                        stack.pop();
                    } else {//栈顶为星号
                        List<Character> list = new ArrayList<>();
                        int oldLen = stack.size();
                        while (!stack.isEmpty()) {
                            char tmpChar = stack.pop();
                            if (tmpChar == '(') {
                                break;
                            } else {
                                list.add(tmpChar);
                            }
                        }
                        if (oldLen == list.size()) {//全是星号
                            list.remove(list.size() - 1);
                        }
                        // 重新装入栈
                        for (int i = list.size() - 1; i >= 0; i--) {
                            stack.push(list.get(i));
                        }
                    }
                    break;
            }
        }
        int startNum = 0, leftNum = 0;
        while (!stack.isEmpty()) {
            char c = stack.pop();
            if (c == '*') {
                startNum++;
            } else {
                leftNum++;
            }
            if (leftNum > startNum) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        boolean flag = new P678().checkValidString("(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())");
        System.out.println(flag);
        Executors.newSingleThreadExecutor();
    }
}
